Private Internet Protocol (IP) address spaces may be employed to prevent exhaustion of the globally unique IP address space and/or to improve security of a distributed computer system. Interconnecting a network using private IP address spaces to the Internet may be performed by a router interconnecting a private network to the Internet, by implementing network address translation (NAT). NAT may involve substituting IP addresses within packets being routed according to a configurable set of rules. In an illustrative example, NAT may be employed for implementing IP masquerading, which is a technique that hides a private IP network behind a single IP address in a different IP address space. Various solutions may be employed for providing inbound connectivity to a private IP network which is connected to the Internet using the IP masquerading technique.